This invention is generally related to interconnection networks for massively parallel computer systems and, more particularly, to vertex symmetric networks with simple routing schemes through these networks.
Parallel computer systems are generally composed of many processors which communicate through an interconnection network. This network can be represented by a graph: a collection of nodes which represent the processors and edges which represent the wires which connect pairs of processors. It is highly desirable to be able to construct interconnection networks which have as many nodes as possible, given a fixed degree (the number of wire pairs connected to each node) and diameter (the maximum number of wires a message must traverse to get between any two processors). It is generally shown by W. G. Bridge et al., "On the Impossibility of Directed Moore Graphs," J. of Comb. Theory 29, 339-341 (1980), that a directed graph with degree d and diameter k can have at most n.sub.max =d.sup.k +d.sup.k+1 +. . . +d nodes. In M. Imase et al., "A Design for Directed Graphs With Minimum Diameter," IEEE Trans. Comp. C-32, 782-784 (1983) graphs are constructed which have n nodes, degree d, and diameter at most k+1 for all n.ltoreq.n.sub.max .
In a parallel processor system, it would be desirable for the network to have vertex symmetry, i.e., any node in the network looks essentially like any other node, wherein the routing algorithm is identical for each node in the network. Some of the graphs taught by the Imase reference have vertex symmetry and the desirable properties of vertex symmetry have been noted, see e.g., J. C. Bermond et al., "Strategies for Interconnection Networks: Some Methods from Graph Theory " J. Parallel Distributed Computing 3, 433-449 (1986).
It would also be desirable to easily expand parallel networks to add additional processors. Such a characteristic would enable a core network to be expanded or several core networks to be interconnected. It would be further desirable for message routing through the network to be accomplished using only simple algorithms for determining the routing path through the network. It is also desirable to minimize the number of routing steps which must be traversed along a routing path between a source processor and a destination processor.
These problems and others are addressed by the present invention, wherein a vertex symmetric routing network is provided for a plurality of processors to enable a shortest routing path through the network to be obtained.
Accordingly, it is an object of the present invention to provide networks having the smallest diameter known for a given degree.
Another object of the present invention is to require relatively simple routing algorithms at each processor for transmitting messages through the system.
Yet another object is to provide identical nodes throughout the network, i.e., each node has the same number of interconnection wires and the routing algorithm is identical for each node in the network.
Still another object of the present invention is to enable the subject networks to be expanded by only simple modifications to the networks.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.